import java.util.Stack;

class Solution {
    public int triangleNumber(int[] nums) {
        sortNums(nums);
        int len = nums.length;
        int count = 0;
        for(int i = len - 1; i > 1; i--){
            int left = 0;
            int right = i - 1;
            while(left < right){
                if(nums[left] + nums[right] > nums[i]){
                    count += (right - left);
                    right--;
                }else{
                    left++;
                }
            }
        }
        return count;
    }
    //快速排序 - 采用非递归的方式
    private void sortNums(int[] nums){
        int left = 0;
        int right = nums.length - 1;
        int mid = partition(nums, left, right);
        Stack<Integer> stack = new Stack<>();
        if(left < mid - 1){
            stack.push(left);
            stack.push(mid - 1);
        }
        if(mid + 1 < right){
            stack.push(mid + 1);
            stack.push(right);
        }
        while(!stack.isEmpty()){
            right = stack.pop();
            left = stack.pop();
            mid = partition(nums, left, right);
            if(left < mid - 1){
                stack.push(left);
                stack.push(mid - 1);
            }
            if(mid + 1 < right){
                stack.push(mid + 1);
                stack.push(right);
            }
        }
    }
    private int partition(int[] nums, int left, int right){
        //这里搞一个三数取中法
        int mid = midOfThree(nums, left, right);
        int tmp = nums[left];
        nums[left] = nums[mid];
        nums[mid] = tmp;
        //挖坑法
        tmp = nums[left];
        while(left < right){
            while(left < right && nums[right] >= tmp){
                right--;
            }
            nums[left] = nums[right];
            while(left < right && nums[left] <= tmp){
                left++;
            }
            nums[right] = nums[left];
        }
        nums[left] = tmp;
        return left;
    }
    private int midOfThree(int[] nums, int left, int right){
        int mid = (left + right) / 2;
        if(nums[left] < nums[right]){
            if(nums[mid] < nums[left]){
                return left;
            }else if(nums[mid] > nums[right]){
                return right;
            }else{
                return mid;
            }
        }else{
            if(nums[mid] > nums[left]){
                return left;
            }else if(nums[mid] < nums[right]){
                return right;
            }else{
                return mid;
            }
        }
    }
}